package graph_depth_first_travelsal_apply.cc;

import graph_depth_first_traversal.Graph;

import java.util.ArrayList;

/**
 * @author sijunqiang
 * @data 2021/6/13 12:49
 * @description: 邻接表的深度优先遍历的应用--之-求图中的联通分量
 * <p>
 * 实现功能：
 * 1：求一个图中联通分量的个数
 * 2: 判断图中两个点是否连接(或者说是否在同一个联通分量上面)
 * 3: 获取图中联通变量所有的顶点
 */
public class Ccount {

    // 定义一个图类对象,用来标记传进来的图对象
    private Graph G;

    // 定义一个int类型数组替代之前的 布尔数组,用来标记图的节点是否已经遍历过
    // 这样的话 就能承载更多的信息  巧妙的是, 同样的数组的角标 代表顶点 索引上面的值代表联通分量的ID
    private int[] visited;

    // 定义一给属性 用来记录图中联通分量的个数
    private int cccount;

    // 构造函数 就是图的深度优先遍历
    public Ccount(Graph G) {
        this.G = G;
        visited = new int[G.V()];

        // -1：代表未被遍历过
        for (int i = 0; i < visited.length; i++) {
            visited[i] = -1;
        }

        for (int v = 0; v < G.V(); v++) {
            if (visited[v] == -1) { //如果图中的顶点在数组中==-1,那么的话说明这个顶点未被遍历过。
                dfs(v, cccount);
                cccount++;
            }
        }
    }

    // 开始图的深度优先遍历
    // ccId 代表联通分量的id 如果索引(在这里索引巧妙是设计为为顶点)上面的值相同的话 说明是同一个联通分量
    private void dfs(int v, int ccId) {
        visited[v] = ccId;// 顶点!=-1,说明该节点已经遍历过。
        // 遍历这个顶点 所相邻的顶点
        for (int w : G.adj(v)) {
            if (visited[w] == -1) {//如果这个顶点中,其中关联的顶点没有被标记过 那么就需要再次的以这个顶点为顶点遍历。
                dfs(w, ccId);
            }
        }
    }

    // 获取图中联通分量的个数
    public int count() {
        return cccount;
    }

    // 判断图中两个顶点是否连接, 其实就是看下这两个顶点是否在同一个联通变量上面。
    public boolean isConnect(int v, int w) {
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v] == visited[w];
    }


    // 获取图中每个联通分量的里面的节点
    public ArrayList<Integer>[] components() {

        //定义一个数组集合,其中每个数组中的元素都是一个集合,用来装联通变量里面的所有的顶点。
        ArrayList<Integer>[] res = new ArrayList[cccount];
        for (int i = 0; i < cccount; i++) {
            res[i] = new ArrayList<>();
        }

        //往数组中添加, 添加顶点
        for (int v = 0; v < G.V(); v++) {
            //visited[v] 得到结果是联通分量的ID; res[visited[v]]得到的结果是 对应数组中的那个联通分量.然后在往这个联通分分量里面添加节点。
            res[visited[v]].add(v);
        }
        return res;
    }


    public static void main(String[] args) {
        Graph graph = new Graph("graph_depth_first_traversal.txt");
        System.out.println(graph);
        Ccount cc = new Ccount(graph);
        System.out.println(cc.count());

        // 判断两个顶点是否连接
        System.out.println(cc.isConnect(0, 6));
        System.out.println(cc.isConnect(0, 5));

        // 获取图中所有的联通分量
        ArrayList<Integer>[] comp = cc.components();
        for (int ccid = 0; ccid < comp.length; ccid++) {
            System.out.print(ccid + " ：");
            for (int w : comp[ccid]) {
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }
}